package io.zouyalong.algo.leetcode;

public class BurstBalloons {
    public static void main(String[] args) {
        var inst = new BurstBalloons();
        var nums = new int[]{8,2,6,8};
        System.out.printf("coin: %d\n", inst.solution1Greedy(nums));
        System.out.printf("solution2: %d\n", inst.solution2Recursive(nums));
        System.out.printf("solution3: %d\n", inst.solution3DP(nums));
    }

    // 不能用
    public int solution1Greedy(int[] nums) {
        int maxPointPos = -1;
        int maxPoint = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxPoint) {
                maxPointPos = i;
                maxPoint = nums[i];
            }
        }
        int totalPoints = 0;
        for (int i = maxPointPos - 1; i >= 0; i--) {
            int leftPoint = i > 0 ? nums[i - 1] : 1;
            totalPoints += maxPoint * nums[i] * leftPoint;
        }
        for (int i = maxPointPos + 1; i < nums.length; i++) {
            int rightPoint = i < nums.length - 1 ? nums[i + 1] : 1;
            totalPoints += maxPoint * nums[i] * rightPoint;
        }
        totalPoints += maxPoint;
        return totalPoints;
    }

    private int lastBurstBalloonWithMaxCoins(int[] nums, int left, int right, int[][] helper) {
        if (left >= right - 1) {
            return 0;
        }
        if (helper[left][right] > 0) {
            return helper[left][right];
        }
        int maxPoint = 0;
        for (int i = left + 1; i < right; i++) {
            int lastPoint = nums[left] * nums[i] * nums[right] + lastBurstBalloonWithMaxCoins(nums, left, i, helper) +
                    lastBurstBalloonWithMaxCoins(nums, i, right, helper);
            if (lastPoint > maxPoint) {
                maxPoint = lastPoint;
            }
        }
        helper[left][right] = maxPoint;
        return maxPoint;
    }

    public int solution2Recursive(int[] nums) {
        int[] wrappedNum = new int[2 + nums.length];
        wrappedNum[0] = 1;
        wrappedNum[nums.length + 1] = 1;
        for (int i = 1; i <= nums.length; i++) {
            wrappedNum[i] = nums[i - 1];
        }
        return lastBurstBalloonWithMaxCoins(wrappedNum, 0, nums.length + 1, new int[2 + nums.length][2 + nums.length]);
    }

    public int solution3DP(int []nums) {
        int n = nums.length;
        int[] wrappedNum = new int[2 + n];
        wrappedNum[0] = 1;
        wrappedNum[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            wrappedNum[i] = nums[i - 1];
        }
        var dp = new int[2 + n][2 + n];

        for (int i = n; i >= 0; i--) {
            for (int j = i+2; j <= n+1; j++) {
                for (int k = i+1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], wrappedNum[i] * wrappedNum[k] * wrappedNum[j] + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][n+1];
    }
}
